package main

// 560. 和为 K 的子数组
func main() {
	nums, k := []int{1, 1, 1}, 2
	//nums, k := []int{1, 2, 3}, 3
	res := subarraySum2(nums, k)
	println(res)
}

func subarraySum2(nums []int, k int) int {
	// 2.使用一个Map，存储每个元素i，和前面所有元素的和为Map[i]
	// 那要获取子数组 j -> i 的和为K，则用 Map[i] - Map[j] = k
	// 那我就可以这么他妈的处理了
	var ans int
	preSum := 0
	preMap := make(map[int]int)

	preMap[0] = 1 // 如果元素i直接等于k，需要这个条件

	for _, n := range nums {
		preSum += n
		if preCount, exists := preMap[preSum-k]; exists {
			ans += preCount
		}
		preMap[preSum] += 1
	}
	return ans
}

func subarraySum(nums []int, k int) int {
	// 1.暴力解法
	ans := 0
	for idx, _ := range nums {
		currSum := 0
		for i := idx; i < len(nums); i++ {
			currSum += nums[i]
			if currSum == k {
				ans++
			}
		}
	}

	return ans
}

//给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
//
//子数组是数组中元素的连续非空序列。
//
//示例 1：
//
//输入：nums = [1,1,1], k = 2
//输出：2
//示例 2：
//
//输入：nums = [1,2,3], k = 3
//输出：2
//
//提示：
//
//1 <= nums.length <= 2 * 104
//-1000 <= nums[i] <= 1000
//-107 <= k <= 107
